package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
		return root2
	}
	if root2 == nil {
		return root1
	}
	root1.Val += root2.Val
	root1.Left = mergeTrees(root1.Left, root2.Left)
	root1.Right = mergeTrees(root1.Right, root2.Right)
	return root1
}
func print(node *TreeNode) {
	if node == nil {
		return
	}
	fmt.Printf("%d->", node.Val)
	print(node.Left)
	print(node.Right)
}
func main() {
	node1 := &TreeNode{
		Val:   1,
		Left:  nil,
		Right: nil,
	}
	node2 := &TreeNode{
		Val:   2,
		Left:  nil,
		Right: nil,
	}
	node3 := &TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node4 := &TreeNode{
		Val:   5,
		Left:  nil,
		Right: nil,
	}
	node1.Left = node3
	node1.Right = node2
	node3.Left = node4

	node5 := &TreeNode{
		Val:   2,
		Left:  nil,
		Right: nil,
	}
	node6 := &TreeNode{
		Val:   1,
		Left:  nil,
		Right: nil,
	}
	node7 := &TreeNode{
		Val:   3,
		Left:  nil,
		Right: nil,
	}
	node8 := &TreeNode{
		Val:   4,
		Left:  nil,
		Right: nil,
	}
	node9 := &TreeNode{
		Val:   7,
		Left:  nil,
		Right: nil,
	}
	node5.Left = node6
	node5.Right = node7
	node6.Right = node8
	node7.Right = node9
	res := mergeTrees(node1, node5)
	print(res)
}
